#include <iostream>
#include <cmath>

using namespace std;

const int N=1000010;
const int MOD=1e9;

int w[N];
int n,f[N];

int main()
{
    cin>>n;
    for(int i=1;i<=21;i++) w[i]=pow(2,i-1);


    f[0]=1;//f表示整数为i的拆分数目
    for(int i=1;i<=21;i++) //每种物品
    {
        for(int j=w[i];j<=n;j++) //价值
        {
            if(j>=w[i]) f[j]=(f[j]+f[j-w[i]])%MOD;
            else break;
        }
    }

    cout<<f[n]<<endl;

    return 0;
}
